#include<stdio.h>
#include<math.h>
//二分法
double dhrt(double a, double b, double eps, int *m, double(*f)(double))
{
    double fa, x, fx;
    fa = (*f)(a);
    while (fabs(a - b)>= eps && *m)
    {
        x = (a + b) / 2.0;
        fx = (*f)(x);
        if (fx*fa < 0)
            b = x;
        else
            a = x;

        (*m)--;
    }

    return x;
}
//不动点迭代法
double dhrt2(double x0, double eps, int *m, double(*g)(double))
{
    double x1;
    x1 = (*g)(x0);
    while (fabs(x1 - x0) >= eps && *m)
    {
        x0 = x1;
        x1 = (*g)(x0);
        (*m)--;
    }
    return x1;
}
//牛顿迭代法
double newt(double x0, double eps, int *m, double(*f)(double),double(*ff)(double))
{
    double x1, f0, ff0;
    f0 = (*f)(x0);
    ff0 = (*ff)(x0);
    x1 = x0-f0/ff0;
    while ((fabs(x1 - x0) >= eps || fabs(f0) >= eps) && *m)
    {
        x0 = x1;
        f0 = (*f)(x0);
        ff0 = (*ff)(x0);
        x1 = x0 - f0 / ff0;
        (*m)--;
    }
    return x1;
}
//弦截法
double newt2(double a, double b, double eps, int *m, double(*f)(double))
{
    double x2, f0, f1, f2;
    f0 = (*f)(a);
    f1 = (*f)(b);
    x2 = b - f1 * (b - a) / (f1 - f0);
    while ((fabs(x2 - a) >= eps || fabs(f1) >= eps) && *m)
    {
        f2 = (*f)(x2);
        a = b;
        f0 = f1;
        b = x2;
        f1 = f2;
        x2 = b - f1 * (b - a) / (f1 - f0);
        (*m)--;
    }
    return x2;
}
//黄金分隔法
double gss(double a, double b, double eps, int *m, double(*f)(double))
{
    double fc,fd,c,d;
    c = a + 0.382*(b - a);d = a + 0.618*(b - a);
    fc = (*f)(c);fd = (*f)(d);
    while (d-c >= eps && *m)
    {
        if (fc > fd)
        {
            a = c;c = d;d= d = a + 0.618*(b - a);
        }
        else
        {
            b = d;d = c;c= c = a + 0.382*(b - a);
        }
        fc = (*f)(c);fd = (*f)(d);
        (*m)--;
    }
    return fc<fd?c:d;
}
double f1(double x)
{
    return (-x*x*x-2*x*x-1)/2.0;
}
double f2(double x)
{
    return x*x*x-2*x*x+4*x+1;
}
double ff2(double x)
{
    return  3*x*x-4*x+4;
}
double f3(double x)
{
    return x*x*x-6*x-1;
}
double f4(double x)
{
    return x*x*x-2*x*x+7*x-4;
}
double f5(double x)
{
    return x*x-4*x+4;
}
int main()
{
    int m=100000;
    printf("(1):%lf\t",dhrt2(-1.5,1e-6,&m,f1));
    printf("(2):%lf\t",newt(0,1e-6,&m,f2,ff2));
    printf("(3):%lf\t",dhrt(2,3,1e-6,&m,f3));
    printf("(4):%lf\t",newt2(0.5,1,1e-6,&m,f4));
    printf("(5):%lf",gss(0,4,1e-6,&m,f5));
}
